Optimization of highly multi-modal and deceptive functions with multiple independent variables is very time consuming due to large search spaces and multiple optima that the functions exhibit. Generally, the more independent variables the functions have, the more difficult the optimization process tends to be.
Functions that are especially difficult to optimize generally share certain characteristics including: multi-modality, non-differentiability, discontinuities, feature-type (non-ordered) variables, and a large number of independent variables. Classical mathematical examples of such functions include for example, Rastringin's function, deceptive functions, Holland's Royal Road function.
There are also numerous practical situations in which the problem is represented by a highly multi-modal and/or deceptive function. Examples of such practical situations include, the choice of routers in computer/wireless networks, organization of transistors on chips, biocomputing applications such as protein folding and RNA folding, evolvable hardware, job-shop scheduling and maintenance scheduling problems, timetabling, tracking of targets by sensor networks, sensor deployment planning tools and the control and management of networks of sensors. The control and management of a network of sensors will be considered further as an exemplary massively multi-modal practical problem.
Unattended ground sensors (“UGSs”) can greatly add to the effectiveness and capability of military operations. Most commercially available UGSs are multi-functional, integrated sensor platforms that operate independently. An example of an UGS is an acoustics UGS, made up of three acoustic microphones (for accurate bearing angle measurements), a seismic transducer, a magnetic sensor, a global positioning sensor, an orienting sensor, integrated communications and signal processing electronics, and a battery. Such a platform is generally about 1 ft3 (28,320 cm3), and is quite expensive. Because of these disadvantages, they are generally not used to support remote surveillance applications for small, rapidly deployable military operations.
An alternative to these relatively bulky, expensive sensor platforms is to use miniature, about 2 in3 (about 33 cm3) UGSs that are inexpensive and easily deployed by a single war fighter. Smaller sensors, such as those utilized in these miniature UGSs, generally have a shorter range of communications and target sensing, and may only be able to sense a single target characteristic (e.g. a seismic vibration or a chemical detection). Further, smaller sensors generally have a shorter operating life because of smaller batteries. Because of these characteristics, many more of these small UGSs would have to be deployed to accomplish the same goal as their larger counterparts. However, individual miniature UGSs functioning alone would be incapable of carrying out the surveillance objectives.
One alternative to this problem is to “overseed” the surveillance region with these small, low cost UGSs and enable these sensors to organize themselves and work together cooperatively. An UGS network such as this would have a number of advantages not found in more bulky unitary functioning sensors. For example, centrally positioned UGSs can serve as “short-haul” communication relays for the more distant sensors. Many more sensors in a network allow for different types of sensors, which would give the collective operation of the network broader functionality. Also, the built in redundancy present in the network would make it less susceptible to single point failures and/or sensor dropouts.
In order for a network of numerous small, inexpensive UGSs to function acceptably, an algorithm and method to organize and control such a network must be developed. The problem of selecting an optimal set of sensors to detect, track, and classify targets entering a surveillance area while at the same time minimizing the power consumption of the sensor network is considered a multi-objective optimization problem to which there is no unique solution. Furthermore, for a linearly increasing number of targets or sensors, optimization will result in a combinatorial search space that increases exponentially.
U.S. Pat. No. 6,055,523 (Hillis) discloses a method for assigning sensor reports in multi-target tracking with one or more sensors. This method receives sensor reports from at least one sensor over multiple time scans, formulates individuals in a genetic algorithm population as permutations of the sensor report, and then uses standard genetic algorithm techniques to find the path of the tracked object. This method uses a genetic algorithm to determine the path of the tracked object, not to select the sensors or sensor reports to utilize.
Therefore, there exists a need for an improved algorithm that can select individual sensors from a network with the goal of optimizing a number of different variables of performance simultaneously.